package com.sicheng.lc.lc笔试.京东篇;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/3 22:24
 */
public class 小红分裂 {
    /**
     * 小红拿到一个数组，每次可以进行如下操作之一：
     * 选择一个x：将其分裂成 1 和 x-1
     * 选择一个x：分裂成 a ，b 满足a*b=x
     * 求最少操作多少次将数组所有元素变成1
     * <p>
     * 输入：
     * 第一行 ： n
     * 第二行n个数： a1 a2 a3 ... an
     * <p>
     * 1<=n，ai <= 1e5
     */

    static int N = (int) 1e5;
    static int[] dp = new int[N + 1];
    static List<Integer>[] g = new List[N + 1];

    static {
        Arrays.setAll(g, k -> new ArrayList<>(50));
        for (int j = 2; j <= N; j++) {
            for (int i = j; i <= N; i += j) {
                g[i].add(j);
            }
        }
        Arrays.fill(dp, Integer.MAX_VALUE >> 1);
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= N; i++) {
            int x = Integer.MAX_VALUE;
            for (int j : g[i]) {
                if (j * j > i)
                    break;
                x = Math.min(dp[j] + dp[i / j], x);
            }
            dp[i] = Math.min(dp[i - 1], x) + 1;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int res = 0;
        for (int x : nums) {
            res += dp[x];
        }
        System.out.println(res);

    }
}
